<?php
// Find nearest value in sorted array
// Note: Use binary search algo.
// Keep start and end position in the array while doing binary searches.
// Update start and end position and then the new search pivot will be the mid value.

require_once 'util.php';

$array = generateRandomArray(0, 100, 50);
//sort( $array );
quick_sort( $array );

$value = 30;

var_dump( $array );

echo "$value is nearest to: ".findNearestValue($array, $value);

function findNearestValue( $array, $value ){
	// Search like a BST
	$length = count( $array );
	if( $length <= 1 ){
		return $array[ 0 ];
	}

	// Larger than array
	if( $value >= $array[ $length - 1 ] ){
		$pos = $length - 1;
		return $array[ $length - 1 ];
	}

	// Smaller than array
	if( $value <= $array[ 0 ] ){
		$pos = 0;
		return $array[ 0 ];
	}

	// Value falls inside array
	$start = 0;
	$end = $length - 1;

	while( $start < $end ){
		$pos = $start + floor( ( $end - $start ) / 2 );

		if( $value > $array[$pos] ){
			if( $value <= $array[ $pos + 1 ] ){
				$pos = (($value - $array[$pos]) > ($array[$pos+1] - $value)) ? $pos+1 : $pos;
				break;
			}
			$start = $pos + 1;
		}
		else if( $value < $array[$pos] ){
			if( $value >= $array[ $pos - 1 ] ){
				$pos = (($value - $array[$pos-1]) > ($array[$pos] - $value)) ? $pos : $pos-1;
				break;
			}
			$end = $pos - 1;
		}
		else {
			// Exact match
			break;
		}
	}

	return $array[ $pos ];
}